package com.googlecode.boliang.q06;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class DeterminePostOrder {

	public boolean isPostOrderSequence(List<Integer> intList) {
		
		List<Integer> lessList = new ArrayList<Integer>(); 
		List<Integer> greaterList = new ArrayList<Integer>(); 
		int pivotValue = intList.get(intList.size() - 1); 
		
		if (intList.size() <= 1) return true;
		
		
		
		Iterator<Integer> iter = intList.iterator(); 
		
		while (iter.hasNext()) {
			int iterValue = iter.next(); 
			if (iterValue < pivotValue) {
				lessList.add(iterValue); 
			} else {
				break;
			}
		}
		
		intList.removeAll(lessList);
		intList.remove(intList.size() - 1); 
		greaterList.addAll(intList); 
		
		for (Iterator<Integer> iterGreater = greaterList.iterator(); iterGreater.hasNext(); ) {
			int iterGreaterValue = iterGreater.next(); 
			if (iterGreaterValue < pivotValue) {
				System.out.println(iterGreaterValue + "<" + pivotValue); 
				return false;
			}
		}
		
		
		if (this.isPostOrderSequence(lessList) && this.isPostOrderSequence(greaterList)) {
			return true;
		}
		
		return false;

	}
}
